package StringPackage;

import java.util.Arrays;

/**
 * @author Lzm
 * @version 1.0
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * 示例 1:
 *
 * 输入: s = "abab"
 * 输出: true
 * 解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 *
 * 输入: s = "aba"
 * 输出: false
 * 示例 3:
 *
 * 输入: s = "abcabcabcabc"
 * 输出: true
 * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 */
public class repeatedSubstringPattern {
  /*本题可以使用暴力求解*/
  /*本题可以使用KMP算法*/
  /*KMP算法解题思路:
  * 1. 将参数s, 两个s合并成一个news
  * 2. 去掉news的首尾字符
  * 3. 判断news是否包括原先的s
  * 若包括原先的s, 则返回true
  * 反之返回false;*/
  public static void main(String[] args) {
    String str = "issip";
    String text = "mississippi";
    System.out.println(StringIsExists(text, str));
  }
  /*下面利用KMP算法来实现判断news是否包括原先的s*/
  /*给定一个字符串, 求其部分匹配值*/
  public static int[] getNext(String str){
    /*初始化*/
    int[] next = new int[str.length()];
    next[0] = 0;
    /*这里, i代表文本串的索引; j代表模式串的索引*/
    for (int i = 1 , j = 0 ; i < str.length() ; i ++){
      /*如果字符不相等*/
      while(j > 0 && str.charAt(i) != str.charAt(j)){
        j = next[j - 1];
      }
      /*如果字符相等*/
      if (str.charAt(i) == str.charAt(j)){
        j++;
      }
      next[i] = j;
    }
    return next;
  }
  /*给定文本串和模式串判断本文串中是否出现了模式串*/
  public static int StringIsExists(String text,String str){
    int[] next = getNext(str);
    for(int i = 0 , j = 0 ; i < text.length() ; i++){
      while(j > 0 && text.charAt(i) != str.charAt(j)){
        j = next[j - 1];
      }
      if (text.charAt(i) == str.charAt(j)){
        j++;
      }
      if (j == str.length()){
        return i - str.length() + 1;
      }
    }
    return -1;
  }
  /*下面这个方法是判断一个字符串是否能由它的字串组成*/
 /* public static boolean repeatedSubstringPattern(String s){
    *//*产生一个由两个s拼接且去掉首尾的新字符串*//*
    String news = s.substring(1,s.length()) + s.substring(0,s.length() - 1);
    *//*如果news中有s字串则返回true, 反之返回false*//*
    boolean result;
    result = StringIsExists(news,s);
    return result;
  }*/
}
